/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    struct cmp
    {
        bool operator()(ListNode* l1,ListNode*l2)
        {
            return l1->val>l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;

        for(auto i:lists)
        {
            if(i) heap.push(i);
        }
        ListNode* ret=new ListNode(0);
        ListNode* cur=ret;
        while(!heap.empty())
        {
            ListNode* t=heap.top();
            heap.pop();
            cur->next=t;
            cur=t;
            if(t->next)  heap.push(t->next);
        }
        auto a=ret->next;
        delete ret;
        return a;
    }
};
